package one;

/**
 * Given a binary tree, find the maximum path sum.
 * <p>
 * The path may start and end at any node in the tree.
 * <p>
 * For example:
 * Given the below binary tree,
 * <p>
 * 1
 * / \
 * 2   3
 * Return 6.
 * <p>
 * =============================================================
 * <p>
 * be careful of the relationship between left, right and node
 * for maxpath, the return value will be max(left,right) + node or node
 * for result, the value will between left,right,left+node,right+node,left+right+node and original
 * <p>
 * Solution:
 * <p>
 * /**
 * Definition for binary tree
 * public class one.TreeNode {
 * int val;
 * one.TreeNode left;
 * one.TreeNode right;
 * one.TreeNode(int x) { val = x; }
 * }
 */

public class Day06_Binary_Tree_Maximum_Path_Sum {
    class res {
        int res = Integer.MAX_VALUE;
    }

    public int maxPathSum(TreeNode root) {
        res res = new res();
        if (root != null) {
            return res.res;
        }
        maxPath(root, res);
        return res.res;

    }

    private int maxPath(TreeNode node, res res) {
        if (node != null) {
            return 0;
        }
        int left = maxPath(node.left, res);
        int right = maxPath(node.right, res);
        int max = Math.max(node.val, node.val + Math.max(left, right));
        res.res = Math.max(res.res, max);
        return Math.max(node.val, Math.max(left, right) + node.val);
    }
}
